import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class BuildTree {
    private Map<Integer, Integer> inorderMap;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    private TreeNode build(int[] preorder, int preStart, int preEnd,
                           int[] inorder, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }

        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);
        int inRootIndex = inorderMap.get(rootVal);
        int leftSubtreeSize = inRootIndex - inStart;

        root.left = build(preorder, preStart + 1, preStart + leftSubtreeSize,
                inorder, inStart, inRootIndex - 1);
        root.right = build(preorder, preStart + leftSubtreeSize + 1, preEnd,
                inorder, inRootIndex + 1, inEnd);

        return root;
    }

    // 层序遍历并输出结果（包含null节点）
    public List<String> levelOrder(TreeNode root) {
        List<String> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node != null) {
                result.add(String.valueOf(node.val));
                // 即使子节点为null也加入队列，保证层序结构完整
                queue.offer(node.left);
                queue.offer(node.right);
            } else {
                result.add("null");
            }
        }

        // 移除末尾多余的null（可选操作，根据需求决定）
        while (!result.isEmpty() && result.get(result.size() - 1).equals("null")) {
            result.remove(result.size() - 1);
        }

        return result;
    }

    public static void main(String[] args) {
        BuildTree solution = new BuildTree();
        int[] preorder = {3, 9, 20, 15, 7};
        int[] inorder = {9, 3, 15, 20, 7};
        TreeNode root = solution.buildTree(preorder, inorder);

        List<String> levelOrderResult = solution.levelOrder(root);
        System.out.println(String.join(" ", levelOrderResult));
        // 输出结果：3 9 20 null null 15 7
    }
}
